// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import "fmt"

// 声明一个名为dp的二维数组，包含 500 行和 500 列，用零初始化
var dp [500][500]int16

func minStep(str1, str2 string) int {
	for i, r1 := range str1 { // 遍历字符串str1的每个字符
		for j, r2 := range str2 { //遍历字符串str2的每个字符
			if r1 == r2 { //如果两个字符相同
				if i != 0 && j != 0 { // 如果两个字符串都有多个字符
					//则将 1 加到前一个索引处存在的数组dp的值
					dp[i][j] = dp[i-1][j-1] + 1
				} else {
					//如果任何一个字符串只有一个字符，则将数组dp的值设置为 1
					dp[i][j] = 1
				}
			} else { //如果两个字符不同
				//如果两个字符串都超过一个字符
				if i != 0 && j != 0 {
					//将数组dp的值设置为左侧和上方索引中存在的值的最大值
					dp[i][j] = max(dp[i-1][j], dp[i][j-1])
				} else if i != 0 {
					// 将数组dp的值设置为上述索引中存在的值
					dp[i][j] = dp[i-1][j]
				} else if j != 0 {
					// 将数组dp的值设置为左侧索引中存在的值
					dp[i][j] = dp[i][j-1]
				} else {
					//如果两个字符串只有一个字符并且都不同，则将数组dp的值设置为 0
					dp[i][j] = 0
				}
			}
		}
	}
	// 返回将str1转换为str2所需的最少步骤数
	return len(str1) + len(str2) - 2*int(dp[len(str1)-1][len(str2)-1])
}

// 返回两个整数中的最大值
func max(x, y int16) int16 {
	if x >= y {
		return x
	}
	return y
}

func main() {
	str1 := "ilovegolang"
	str2 := "golang"
	res := minStep(str1, str2)
	fmt.Println(res)
}

//$ go run interview12-3.go
//5
